Garbage Collection (hereinafter, simply referred to as “GC”) is widely used so as to safely and automatically collect objects which are allocated by a program during execution thereof. To perform the GC in a multi-thread application where a plurality of threads operate in parallel and share a storage area, all the application threads (hereinafter, simply referred to as “threads”) need to be stopped. This means a degraded responsiveness of the processing. In a web application and other applications where responsiveness is a significant issue, occurrence of pauses due to the GC is a cause for concern.
A conventional technique for solving the above problems is disclosed in Japanese Patent No. 3939975, hereinafter referred to as Patent Document 1. A garbage collection device according to Patent Document 1 includes: allocation means, at the start of execution of methods constituting an application program, for allocating a memory area for each method, and recording correspondences between the allocated memory areas and the methods as well as relationships between the allocated memory areas in terms of the time when they were allocated; moving means, in the case where an object in a first memory area for a first method is referenced from a second memory area for a second method which has been allocated prior to the first memory area, for moving the object to the second memory area; and releasing means, upon completion of one of the methods, for releasing the memory area corresponding to the method.
Another conventional technique for solving the above problems is disclosed in Japanese Unexamined Patent Publication No. 2001-184254, hereinafter referred to as Patent Document 2. The technique of Patent Document 2 is used in an information processor which includes: reference and update prohibiting means for prohibiting an object located in a first space from being referenced or updated by a program prior to initiation of a garbage collection; and exceptional processing performing means, in the case where the garbage collection is executed and a process of referencing and updating the object that has been prohibited from being referenced or updated is to be performed by the program, for performing exceptional processing that does not hamper that process; wherein the technique is characterized in that, as the exceptional processing, the object that is to be referenced and updated by the program, which has been prohibited from being referenced or updated in the first space, is copied into a second space, and a pointer pointing to the object is altered to a pointer pointing to the new copy of the object in the second space.
There is yet another conventional technique for solving the above problems according to which, assuming that most objects are unreachable from threads other than its creator thread during its lifetime, objects are collected in the state where not all the threads are stopped (which technique is hereinafter referred to as a “thread-local GC”) (see T. Domani et al. “Thread-Local Heaps for Java.” Proceedings of the International Symposium on Memory Management, pp. 76-87, 2002, hereinafter referred to as Non-Patent Document 1, and expressly incorporated herein by reference in its entirety for all purposes). In the thread-local GC, each thread is provided with a local area dedicated to the thread where objects are allocated, and each object is assigned an attribute (hereinafter, also referred to as a “shared object attribute”) indicating whether the object is reachable from more than one thread. When a thread is about to write a pointer into a field of an object, software write barrier is executed, and the attribute of any object that would likely be referenced by another thread (hereinafter, referred to as a “shared object”) is changed to “shared”.
Thereafter, when one of the local areas has become full or exhausted, a GC is performed for that exhausted area, so as to collect any objects that are no longer necessary (or, unwanted objects) from among the objects having an attribute other than “shared”. According to the thread-local GC, any shared object that may be referenced by another thread is identified on the basis of its attribute and refrained from being collected. This eliminates the need of suspending the other threads.
In the thread-local GC, however, a shared object cannot be collected or copied to another area because it would likely be referenced by another thread. This causes fragmentation in the local area in the thread-local GC. Although the number of shared objects that are left in a local area after one-time thread-local GC may be small, as the same local area is used repeatedly, the fragmentation will become noticeable, and thus the need of assigning another local area may possibly arise.
A conventional technique for solving the above-described problem of fragmentation is disclosed in Japanese Unexamined Patent Publication No. 2009-37546, hereinafter referred to as Patent Document 3. According to the technique of Patent Document 3, a memory is provided with a thread-local area which is assigned to each of one or more threads that are generated in correspondence with a program and operate in parallel, and a global area which is shared by the threads. Data which is referenced exclusively by a thread is allocated in the thread-local area, while data which is referenced by other threads is allocated in the global area, and in the case where the data in the thread-local area is to be referenced by one of the other threads, the data that would likely be referenced is moved to the global area before it is actually referenced.
Another conventional technique for solving the above problem of fragmentation is disclosed in Japanese Unexamined Patent Publication No. 2004-246753, hereinafter referred to as Patent Document 4. According to the technique of Patent Document 4, an object generated by an application program is arranged in a thread-local heap that is associated with a thread, and when the threads that can reference the generated object are changed, the object is moved to an appropriate thread-group heap (that corresponds to the set of threads that can reference that object). At the lime of collecting an object that is no longer necessary, only the threads that are able to reference the unwanted object are stopped.
There is yet another conventional technique of combining a copy-based concurrent GC with transactional memory that has been widely studied as a way of reducing the synchronization overhead for shared objects (see Phil McGachey et al., “Concurrent GC Leveraging Transactional Memory”, in Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 217-226, 2008, referred to hereinafter as Non-Patent Document 2).